package Algorithm.handleString;

/**
 * 5. 最长回文子串 https://leetcode.cn/problems/longest-palindromic-substring
 * 题目简述：找出一个字符串中的最长回文连续子串。
 */
public class LongestPalindrome {

    public static void main(String[] args) {
        new LongestPalindrome().longestPalindrome("babad");
    }

    /**
     * 思路：中心扩散法。遍历每个字符作为中心的最大回文串。注意回文子串的两种形式：第一种形式：i直接构成中心；第二种形式：i-1和i共同构成中心
     */
    public String longestPalindrome(String s) {
        String maxPa = s.charAt(0)+"";
        for(int i=1;i < s.length();i++) {
            int l = i-1, r = i+1;//第一种形式：i直接构成中心
            while(l >= 0 && r < s.length()) {
                if(s.charAt(l) != s.charAt(r))
                    break;
                else {
                    l--;
                    r++;
                }
            }
            if(r-l-1 > maxPa.length())
                maxPa = s.substring(l+1, r);
            l = i-1;r=i;//第二种形式：i-1和i共同构成中心
            while(l >= 0 && r < s.length()) {
                if(s.charAt(l) != s.charAt(r))
                    break;
                else {
                    l--;
                    r++;
                }
            }
            if(r-l-1 > maxPa.length())
                maxPa = s.substring(l+1, r);
        }
        return maxPa;
    }
}
